Komputer for Alle 2003 Ekstra 100 Spil/K-CD_2003_Ekstra_100_Spil.iso/Board/4free/4free.exe/{app}/Engines/Velena/Readme.txt

Text File | 2002-01-29 | 20KB | 564 lines

                 -+- Velena -+-

A Connect 4 Expert System which Plays Perfectly
================================================



                   Abstract
                   ========

Velena is a Shannon-C type engine written to play
Connect Four. It's based on a knowledged approach that
uses eight mathematical rules to take its decisions.
Since the rules are proven to be correct, the
conclusions made by the engine are also correct. In
this way it has been possible to show that Connect Four
is a first player win and Velena is always able to win
when she plays first.

==================================================


1. Overview
===================

    1.1. Freeware agreement
    =======================

    This engine is to be considered freeware, which
    means that you can use and distribute it to anyone
    you want, provided no fee is charged. You should
    also not disassemble modify or reverse engineer
    the engine for any reason in any circumstance.

         The author's current address is:
                         Giuliano Bertoletti
                         Via Bocchialini n.6
                         Cap. 43100, Parma.
                         Italy

                         E-Mail: [e-mail]
                         Fidonet: 2:332/801.6



    1.2. Greetings
    ==============

    The Velena engine is based on the knowledged
    approach of L.Victor Allis who designed and
    implmented a sophisticated AI engine in a
    program called Victor. Velena uses the same
    strategy, except that even newer concepts and
    techinques were introduced in order to reduce
    the problem complexity (of solving the game)
    to a more tractable factor of magnitude.

    I also thank Filippo Ghilardi who helped me to
    build the opening book data base which took
    several days of work on his Pentium 133 computer.


2. Introduction into Connect Four
=================================

Now I'll describe the rules of the game as well as
some nomenclature used throughout this manual and
some basic connect four strategy.


    2.1. Game Rules
    ===============

    Connect Four is a two players game which takes
    place on a 7x6 rectangular board placed vertically
    between them. One player has 21 'white' men and
    the other 21 'black' men. Each player can drop
    a man at the top of the board in one of the seven
    columns; the man falls down and fills the lower
    unoccupied square. Of course a player cannot drop
    a man in a certain column if it's already full
    (i.e. it already contains six men).

    Even if there's no rule about which color should
    play first, in order to avoid confusion we will
    assume, as in chess, 'white' always plays first.

    Note however that 4Free displays men in
    non-white/black colors even if refered here as
    white and black respectively. Therefore when
    playing with 4Free, we call 'white' the color of
    the player who plays first.

    The object of the game is to connect four men
    vertically, horizontally or diagonally. If the
    board is filled and no one has alligned four men
    then the game is drawn (that is after 42 moves if
    no one wins).

    Here's an example of a game won by white (O) and
    black (X) in fig.1 and fig.2 respectively. A
    possible draw is represented in fig.3


      .......          .......           oooxooo
      .......          .......           xxxoxxx
      .......          .xo....           oooxooo
      ...x...          .xxo...           xxxoxxx
      ...x...          .oox...           oooxooo
      xoooo..          .oxox..           xxxoxxx

       Fig.1            Fig.2             Fig.3
   White (O) wins   Black (X) wins   The Game is drawn


    2.2. Nomenclature
    =================

    Since we need a way for representing a sequence
    of moves instead of a position, I will use the
    same nomenclature as the one used for chess. This
    means that columns are named from A to G, starting
    from left, and rows are numbered from 1 to 6
    starting from the bottom. In this way we could
    represent each square of the board with a pair
    letter-number. For example the square in the
    middle of the lowest row is d1. The square above
    is d2 and the square on the left of d1 is c1.
    (see fig. 3)

               6 . . . . . . .
               5 . . . . . . .
               4 . . . . . . .
               3 . . . . . . .
               2 . . . . . . .
               1 . . . . . . .
                 A B C D E F G

                    Fig. 3


    In this way we could write down a game as a
    sequence of moves. For example the endgame of
    fig.1 could have arisen from the following
    sequence of moves:

        1) d1,d2
        2) c1,d3
        3) b1,a1
        4) e1++

    where ++ indicates the player who did that move
    won the game (as in chess).


    2.3. Game Strategy
    ==================

    There are two kinds of strategies in connect four.
    The first consist in looking ahead few moves to
    avoid the opponent to win and in the same time
    trying to connect four men. The other is looking
    for a win in the long run.

    Virtually all the algorithms I have seen tend to
    implement the first strategy with some variants of
    alpha beta search and the most sophisticated ones
    with tree branch pruning. These strategies assure
    more or less the unvulnerability in the short run,
    but they are doomed to fail in the long run
    because they cannot see beyond the horizzon of few
    plies.

    Most of the games ends between 35th and 42nd move
    when you (or the opponent) are forced to make a
    particular move since there's only one column
    available. In this circumstance most of the people
    believe that the winner is lucky (if there's one).
    That's not it. An expert player is able to make
    this happen much time before. Actually this is
    what Velena does.

    The first step consist in noting that after white
    has moved, an odd number of free squares remains
    on the board. Similary after black has moved an
    even number of free square remains. When there's
    only one column available it's clear that the last
    square will be occupied by black (if no one wins
    first).

    Now let introduce some definitions before
    continuing:

    --------------------------------------------------

    ODD SQUARE: it's a square belonging to an odd row.
    For example d1,c1,c3, f5 are all odd squares.

    EVEN SQUARE: same as above except that the row is
    even. For example a2, b4,c6,e2 are all even
    squares.

    GROUP: it's a set of four squares connected
    horizzontally, vertically or diagonally. The first
    player who fills a group with his men, wins.

    THREAT: it's a group filled with three men of the
    same color which has the fourth square empty, and
    also the square below the empty square is
    empty.

    ODD THREAT: it's a therat in a group whose empty
    square is odd.

    EVEN THREAT: same as above but the empty square
    is even.

    DOUBLE THREAT: they are two groups which share an
    empty odd square; each group is filled with only
    two men (of the same color) and the other two
    squares (one for each group) are empty and are one
    above the other. The square below the shared
    square must be empty too.

    --------------------------------------------------

    It's then clear that if white has an odd threat
    and black cannot connect four men anywhere, the
    game will be eventually won by white.

    Please note that this is a sufficient condition
    and if black can connect four men somewhere,
    further knowledge is required.

    Similary if black has an even threat and white
    cannot connect four men the game will be
    eventually won by black.

    It's clear that in both cases we assume that
    players make the best move available.

    Things get more complex when both players have at
    least one group in which they can connect four
    men. In this case we need further investigation.

    If white has an odd threat and black has an even
    threat and the columns in which the threats are
    (i.e. the empty square) are different then white
    can still win. Of course no player must be able to
    connect four men except in the group in which he
    has the odd/even threat stated above.

    But if columns are the same then the lower threat
    (i.e. the lower empty square) wins.

    If both players have an odd threat the game will
    be drawn. Unless one of them can connect four men
    elsewhere.

    Then the strategy for white is to try to obtain an
    odd threat and for black an even threat. This is
    not always sufficient as the restrictions above
    shows but it's a good starting point to play
    connect four, especially when both players are
    humans.


    2.4. The Way Velena Plays
    =========================

    When set to her strongest level, Velena uses two
    different strategies according she's playing white
    or black. In both cases she uses a database for
    the opening lines. The database is made in such a
    way that Velena is always able to reach a position
    in which she has an odd threat when she plays white
    (and from there she's able to continue and win by
    herself). She tries to follow the longest winning
    line for white when she plays with black. The built
    in evaluation function which examines the positions
    is then sufficient to play the middle and end game.
    However, further search is done just to check for
    trivial wins few moves ahead.


    2.5. Drawbacks of the algorithm
    ===============================

    Connect Four is not complex like chess. Therefore
    moves tends to repeat many times. For example the
    winning line for white is very narrow, so narrow
    that the first seven moves for white are forced.
    This is the reason why Velena is forced to answer
    almost always in the same way, given the same
    position on the board. There are not many
    variants.

    It's not strange that a player who keeps white men
    and learns how to win a game, is then always able
    to win each time he plays. This because he can
    play the same game each time.

    Another drawback is that Velena pays very poor
    attention to distinguish between a win for black
    and a draw. They are almost the same thing for
    her.

    Also note that Velena does the best move (when
    playing with white) only when she starts from the
    empty board. If someone sets up a position and
    then tells the computer to continue the game from
    that point, it's not warranted that the computer
    plays at best.

    Finally the algorithm tend to resign when a game
    is compromised and doesn't fight until the end.

3. Why Velena is so special
===========================

As already said before, Velena is an expert system
able to play the game perfectly. This means that if
the engine is set to it's maximum level of strength
she always wins when she plays first and she is almost
impossible to beat when she plays second (until you
make a few games and you will learn how to beat her by
the engine itself).

Of course if you are a beginner you can set a lower
difficulty level for the computer. This is useful if
you are interested in learning how to play.


    3.1. Game complexity
    ====================

    Although at first sight Connect Four doesn't seem
    a very complex game in terms of combinations of
    moves and the number of reachable different
    positions on the board, it should be noticed that
    it's not a so trivial game as it looks. Let's see
    some mathematics behind it.

    First we can make a raw estimation of game
    complexity noting that since each square can be
    empty or occupied by either white or black, each
    square can be in only three different states,
    leading a total game complexity of 3^42 which is
    in the order of 10^20. Of course this is an upper
    bound which takes in count also the illegal
    positions.

    It is possible to make some finer estimations that
    reduces the number of legal positions, anyway even
    the finest estimation gives us an order of
    magnitude of 7.1 x 10^13, which is still to high
    for a complete enumeration. To build up a brute
    force attack several terabytes of disk space would
    be required, and current technology is far away
    from this possibility. Besides the space
    requirements, also the time requirements would be
    out of what are called "reasonable resources".
    Finally it would be almost impossible to distribute
    the engine.


    3.2. So Velena is not a brute force attack?
    ==================================================

    Definitly not. Velena is an intelligent engine
    which is able to predict the final result of a game
    using complex mathematics, and efficient search
    strategies. The engine is compact and strong; only
    a tiny opening book of about 60.000 positions is
    used for the opening lines. All the rest is
    calculated on fly.


    3.3. Why should I use Velena if it's unbeatible?
    ==================================================

    Well, there are several reasons why this engine
    can be useful. First it represents the final word
    on Connect 4 (or so I hope): no program or living
    man can outperform Velena.

    Besides, Velena is very useful to train yourself
    against a human player. If you want to become a
    strong player then you should train yourself with
    a strong player. And Velena is the strongest.


    3.4. But is Velena really so perfect?
    =====================================

    Well, it's perfect in the sense that she's always
    able to win if she plays first. This because it can
    be mathematically shown that Connect Four can be
    won by the player which plays first (if it plays
    well) no matter how good the opponent is.

    Of course if Velena plays second, there's still a
    chance for the human player to defeat her. Once you
    learned how, you can easiliy win. More over the
    purpose of the computer in this case (when playing
    second) is not to win, but to avoid losing, if
    possible. In other words Velena considers a draw a
    good result if it plays with red men.


    3.5. So Velena destroyed Connect Four?
    ======================================

    Yes, but humans are humans and machines are
    machines. Connect Four is still interesting if
    played between two men. Of course there are no
    chances between a man and a computer, like there
    are no chances between a man and a car. The latter
    will run always faster.


    3.6. Why does Velena play almost always the same
    game when she's in autoplay?
    ==================================================

    Connect four is not like chess. Even if the game
    is not as trivial as tic tac toe, the complexity
    is much smaller than chess. This of course leads
    to a limited number of variants and often the moves
    are forced. For example there's only one winning
    way for white and the first seven moves are forced
    for him. If he choses another move, black can draw.
    Similary black has only one strong defensive line
    (which of course fails in the long run) which can
    protect him from a premature loss. It's clear that
    once you learn how to infiltrate in this line,
    you are likely to win each time against black.


    3.7. Where can I find the complete description of
    the algorithms used here?
    ==================================================

    You can try:

    ftp://ftp.cs.vu.nl/~victor/connect4.zip
    ftp://ftp.cs.vu.nl/~victor/thesis.zip

    this is the documentation made available by
    L.Victor Allis and surely it's very interesting.
    Of course I am not sure that it will be there
    forever. Please contact [e-mail] for more
    information.

    Keep also in mind that this engine is based on his
    theory but it does not follow it completely. For
    example the mathematical rules have been reduced
    from nine to eight.

    You can also refer to Velena Home Page at:
    http://www.ce.unipr.it/~gbe/velena.html


    3.8. Where can I get the last version of the
    Original Velena program?
    ===============================================

    Check out Velena's Home Page at:

    http://www.ce.unipr.it/~gbe/velena.html
    or use a net serach engine.


    3.9. Is the source code of Velena available to
    the public?
    ==================================================

    No, at the moment it's not. Maybe one day it will.


    3.10. Who's F.Alinovi and why did he say:
    "...who wants to make four?"
    ==================================================

    He's a friend. After I bored him telling the inner
    workings of Velena and the clever idea behind the
    algorithm he answered that way. He also added that
    I was losing my time. Poor little fellow! :))))


    3.11. What's "a Shannon-C type program" mean?
    =============================================

    In his famous paper in 1950 C.Shannon describes
    three methods by which a machine could play a
    strategy game (such chess, checkers, connect four
    and so on...). The C-type method consist in
    emulating human mind to take decisions. In other
    words the eight mathematical rules Velena uses are
    not based on a search algorithm but on the
    properties of the game. The A-type method instead
    is based on pure brute force search. Just to be
    fair Velena is not only a Shannon-C type engine
    since it also uses some search algoritms to play,
    anyway the great difference in playing capabilities
    relies just on this knowledged approach, which
    made possible to solve the game.


    3.12 Why isn't there the possibility to change the
    board size?
    ==================================================

    I think the standard 7x6 board is enough. Other
    sizes are not very interesting. For example it can
    easily be shown that black can draw on any (2n)x6
    board. Here's the 6x6 board algorithm black can
    use to draw any game.

    step 1: if white plays column A,B,E or F, you play
            follow up (the same column).

    step 2: when white plays column C or D for the
            first time you answer in the other column.

    step 3: if white plays column C or D again you
            answer in the same column until the column
            is full. If you cannot answer that way
            because the column is full, then you play
            the other column.

    If black follows these three steps, the game can
    be drawn, no matter what white does.


    3.13 Why did you call her Velena?
    =================================

    I don't know, I simply liked the name. However
    it's very similar to "Veleno" which in italian
    means "poison". The intro logo from the original
    game recalls this sensation too. I have nothing
    else to say about it. :-(((



======================================================

    Further details will be given if requested. Please
    write in english or in italian.

======================================================

                                The author:
                                Giuliano Bertoletti
                                Via Bocchialini n.6
                                Cap. 43100 Parma
                                [e-mail]